package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月19日 下午1:00:06 最少添加多少次括号 才使一个括号表达式合法
 * MinimumAddToMakeParenthesesValid_921.java
 * description:用栈的思想 AC 100%
 */
public class MinimumAddToMakeParenthesesValid_921 {
	public int minAddToMakeValid(String S) {
        char []chars=S.toCharArray();
        int top=0;
        int res=0;
        for(char c:chars) {
        	if(c=='(') {
        		top++;
        	}
        	else {
        		if(top==0)
        			++res;
        		else
        			--top;
        	}
        }
        return res+top;
    }
}
